#ifndef LEETCODE_CN_CPP_PROBLEMS_4_H
#define LEETCODE_CN_CPP_PROBLEMS_4_H

#include <algorithm>
#include <vector>

using namespace std;

namespace problem_4
{

class Solution
{
private:
    int getKth(const int *nums1, int size1, const int *nums2, int size2, int k)
    {
        if (size1 == 0)
        {
            return nums2[k];
        }
        else if (size2 == 0)
        {
            return nums1[k];
        }
        int mid1 = size1 / 2, mid2 = size2 / 2;
        if (nums1[mid1] > nums2[mid2])
        {
            return getKth(nums2, size2, nums1, size1, k);
        }

        if (mid1 + mid2 + 1 > k)
        {
            // 去除nums2后半部分
            return getKth(nums1, size1, nums2, mid2, k);
        }
        else
        {
            // 去除nums1前半部分
            return getKth(nums1 + mid1 + 1, size1 - mid1 - 1,
                          nums2, size2,
                          k - mid1 - 1);
        }
    }

public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int total = nums1.size() + nums2.size();
        int res = getKth(nums1.data(), nums1.size(), nums2.data(), nums2.size(), total / 2);
        if (total % 2 != 0)
        {
            return res;
        }
        res += getKth(nums1.data(), nums1.size(), nums2.data(), nums2.size(), (total - 1) / 2);
        return res * 0.5;
    }
};

} // namespace problem_4

#endif //LEETCODE_CN_CPP_PROBLEMS_4_H